/LMAR=0/XLINE=4/FONT#0=BASL30/FONT#1=BASB30/FONT#5=ASI30[LSP,JRA]/FONT#2=ASI30[LSP,JRA]/FONT#3=SUB/FONT#4=SET1/FONT#6=GRK30/FONT#7=SUP/FONT#8=SPEC[LSP,JRA]/FONT#9=BUCK75/FONT#10=GRFX25[LSP,JRA]/FONT#11=METSB/FONT#12=NGB30/FONT#13=GERM35/FONT#14=MG[LSP,JRA]/FONT#15=GRFX35
␈↓ α←␈↓␈↓␈↓ 	DPreface     i␈↓








␈↓"β␈↓ α←␈↓␈↓	Preface␈↓












␈↓"β␈↓ α←␈↓¬␈↓ β'"...␈α∩it␈α⊃is␈α∩important␈α⊃not␈α∩to␈α⊃lose␈α∩sight␈α⊃of␈α∩the␈α⊃fact␈α∩that␈α⊃there␈α∩is␈α⊃a
␈↓ α←␈↓¬␈↓ β'difference␈αbetween␈αtraining␈αand␈αeducation.␈α If␈αcomputer␈αscience␈αis␈α
a
␈↓ α←␈↓¬␈↓ β'fundamental␈α∃discipline,␈α∃then␈α∃university␈α∃education␈α∃in␈α∃this␈α∀field
␈↓ α←␈↓¬␈↓ β'should␈α∀emphasize␈α∪enduring␈α∀fundamental␈α∪principles␈α∀rather␈α∪than
␈↓ α←␈↓¬␈↓ β'transient current technology."

␈↓"β␈↓ α←␈↓␈↓ β'␈↓ ∧zPeter Wegner, ␈↓αThree Computer Cultures␈↓ [Weg 70]         


␈↓"λ␈↓ α←␈↓This␈α⊃text␈α⊃is␈α⊃nominally␈α⊃about␈α∩LISP␈α⊃and␈α⊃data␈α⊃structures.␈α⊃However,␈α∩in␈α⊃the
␈↓ α←␈↓process␈α∞it␈α
covers␈α∞much␈α
broader␈α∞areas␈α
of␈α∞computer␈α
science.␈α∞ The␈α∞author␈α
has
␈↓ α←␈↓long␈α
felt␈α∞that␈α
the␈α∞beginning␈α
student␈α
of␈α∞computer␈α
science␈α∞has␈α
been␈α∞getting␈α
a
␈↓ α←␈↓distorted␈α
and␈α
disjointed␈α
picture␈α
of␈α
the␈α
field.␈α
In␈α
some␈α
ways␈α
this␈α∞confusion␈α
is
␈↓ α←␈↓natural;␈α∪the␈α∪field␈α∀has␈α∪been␈α∪growing␈α∀at␈α∪such␈α∪a␈α∀rapid␈α∪rate␈α∪that␈α∀few␈α∪are
␈↓ α←␈↓prepared␈α∂to␈α∂be␈α⊂judged␈α∂experts␈α∂in␈α∂all␈α⊂areas␈α∂of␈α∂the␈α∂discipline.␈α⊂ The␈α∂current
␈↓ α←␈↓alternative␈α∞seems␈α∞to␈α∂be␈α∞to␈α∞give␈α∞a␈α∂few␈α∞introductory␈α∞courses␈α∂in␈α∞programming
␈↓ α←␈↓and␈α
machine␈α
organization␈α
followed␈αby␈α
relatively␈α
specialized␈α
courses␈α
in␈αmore
␈↓ α←␈↓technical␈α∀areas.␈α∀The␈α∀difficulty␈α∀with␈α∀this␈α∀approach␈α∀is␈α∀that␈α∀much␈α∀of␈α∪the
␈↓ α←␈↓technical␈α≤material␈α≠never␈α≤gets␈α≤related.␈α≠The␈α≤student's␈α≤perspective␈α≠and
␈↓ α←␈↓motivation␈α
suffer␈α
in␈α
the␈α
process.␈α
This␈α
book␈α
uses␈α
LISP␈α
as␈α
a␈α
means␈α
for␈α
relating
␈↓ α←␈↓topics␈α
which␈α
normally␈α
get␈α
treated␈α
in␈α
several␈α
separate␈α
courses.␈α
The␈α
point␈α
is␈α
not
␈↓ α←␈↓that␈α
we␈α
␈↓¬can␈↓␈α
do␈α
this␈α
in␈α
LISP,␈α
but␈α
rather␈α
that␈α
it␈α
is␈α
␈↓¬natural␈↓␈α
to␈α
do␈α
it␈α
in␈α
LISP.
␈↓ α←␈↓The␈α∃high-level␈α∃notation␈α∃for␈α∃algorithms␈α∃is␈α∃beneficial␈α∃in␈α⊗explaining␈α∃and
␈↓ α←␈↓␈↓ii  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓understanding␈α
complex␈α
algorithms.␈α
 The␈αuse␈α
of␈α
abstract␈α
data␈α
structures␈αand
␈↓ α←␈↓abstract␈α⊃LISP␈α⊃programs␈α⊂shows␈α⊃the␈α⊃intent␈α⊂of␈α⊃structured␈α⊃programming␈α⊂and
␈↓ α←␈↓step-wise␈α
refinement.␈α
Much␈α
of␈α
the␈α
current␈α
work␈α
in␈α
mathematical␈α
theories␈α
of
␈↓ α←␈↓computation␈αis␈αbased␈αon␈αLISP-like␈αlanguages.␈αThus␈αLISP␈αis␈αa␈αformalism␈αfor
␈↓ α←␈↓describing␈α∂algorithms,␈α∂for␈α∂writing␈α∂programs,␈α∂and␈α∂for␈α∂proving␈α∂properties␈α∞of
␈↓ α←␈↓algorithms.␈α∂ We␈α∂use␈α∂data␈α∂structures␈α⊂as␈α∂the␈α∂main␈α∂thread␈α∂in␈α⊂our␈α∂discussions
␈↓ α←␈↓because␈α∩a␈α∩proper␈α⊃appreciation␈α∩of␈α∩data␈α∩structures␈α⊃as␈α∩abstract␈α∩objects␈α∩is␈α⊃a
␈↓ α←␈↓necessary prerequisite to an understanding of modern computer science.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α⊂importance␈α⊂of␈α⊂abstraction␈α⊃obviously␈α⊂goes␈α⊂much␈α⊂farther␈α⊃than␈α⊂its
␈↓ α←␈↓appearance␈αin␈αLISP.␈αAbstraction␈αhas␈αoften␈αbeen␈αused␈αin␈αother␈α
disciplines␈αas
␈↓ α←␈↓a␈αmeans␈αfor␈αcontrolling␈αcomplexity.␈α
In␈αmathematics,␈αwe␈αfrequently␈αare␈αable␈α
to
␈↓ α←␈↓gain␈αnew␈αinsights␈αby␈αrecasting␈αa␈αparticularly␈αintransigent␈αproblem␈αin␈αa␈αmore
␈↓ α←␈↓general␈α↔setting.␈α↔ Similarly,␈α↔the␈α_intent␈α↔of␈α↔an␈α↔algorithm␈α↔expressed␈α_in␈α↔a
␈↓ α←␈↓high-level␈α∞language␈α∞like␈α∞Fortran␈α∞or␈α∞PL/1␈α∞is␈α∞more␈α∞readily␈α∞apparent␈α∞than␈α∞its
␈↓ α←␈↓machine-language␈α⊗equivalent.␈α⊗ These␈α⊗are␈α⊗both␈α⊗examples␈α⊗of␈α⊗the␈α⊗use␈α∃of
␈↓ α←␈↓abstraction.␈α∂Our␈α∞use␈α∂of␈α∂abstraction␈α∞will␈α∂impinge␈α∞on␈α∂both␈α∂the␈α∞mathematical
␈↓ α←␈↓and␈αthe␈αprogramming␈αaspects.␈α Initially,␈αwe␈αwill␈αtalk␈αabout␈αdata␈αstructures␈αas
␈↓ α←␈↓abstract␈α∩objects␈α∩just␈α∪as␈α∩the␈α∩mathematician␈α∪takes␈α∩the␈α∩natural␈α∪numbers␈α∩as
␈↓ α←␈↓abstract␈α⊂entities.␈α⊂We␈α⊂will␈α⊂attempt␈α⊂to␈α⊂categorize␈α⊂properties␈α⊂common␈α⊃to␈α⊂data
␈↓ α←␈↓structures␈α∞and␈α∞introduce␈α∞notation␈α∂for␈α∞describing␈α∞functions␈α∞defined␈α∂on␈α∞these
␈↓ α←␈↓abstractions.␈α⊂At␈α⊂this␈α⊃level␈α⊂of␈α⊂discussion␈α⊂we␈α⊃are␈α⊂thinking␈α⊂of␈α⊃our␈α⊂LISP-like
␈↓ α←␈↓language␈α
primarily␈αas␈α
a␈αnotational␈α
convenience␈αrather␈α
than␈α
a␈αcomputational
␈↓ α←␈↓device.␈α∃ However,␈α∃after␈α∃a␈α∃certain␈α∃familiarity␈α∃has␈α∃been␈α∃established␈α∃it␈α∀is
␈↓ α←␈↓important␈αto␈αlook␈αat␈αour␈αwork␈αfrom␈αthe␈αviewpoint␈αof␈αcomputer␈αscience.␈αHere
␈↓ α←␈↓we␈α⊂must␈α⊂think␈α⊂of␈α⊂the␈α⊂computational␈α⊂aspects␈α⊂of␈α⊂our␈α⊂notation.␈α⊂We␈α⊂must␈α∂be
␈↓ α←␈↓concerned␈α∩with␈α∩the␈α∩representational␈α∩problems:␈α∩implementation␈α∩on␈α∩realistic
␈↓ α←␈↓machines,␈α∀and␈α∀efficiency␈α∪of␈α∀algorithms␈α∀and␈α∪data␈α∀structures.␈α∀However,␈α∪it
␈↓ α←␈↓cannot␈αbe␈αover-emphasized␈αthat␈αour␈αneed␈αfor␈αunderstanding␈αis␈αbest␈αserved␈αat
␈↓ α←␈↓the␈α⊂higher␈α⊂level␈α⊂of␈α⊂abstraction;␈α∂the␈α⊂advantage␈α⊂of␈α⊂a␈α⊂high-level␈α⊂language␈α∂is
␈↓ α←␈↓notational␈α∩rather␈α∩than␈α∩computational.␈α∩That␈α⊃is,␈α∩it␈α∩allows␈α∩us␈α∩to␈α∩think␈α⊃and
␈↓ α←␈↓represent␈α
our␈α
algorithms␈α∞in␈α
mathematical␈α
terms␈α
rather␈α∞than␈α
in␈α
terms␈α∞of␈α
the
␈↓ α←␈↓machine.␈α It␈αis␈αafter␈αa␈αclear␈αunderstanding␈αof␈αthe␈αproblem␈αis␈αattained␈αthat␈α
we
␈↓ α←␈↓should begin thinking about representation.
␈↓"β␈↓ α←␈↓␈↓ β'We␈αcan␈αexploit␈αthe␈α
analogy␈αwith␈αtraditional␈αmathematics␈αa␈α
bit␈αfurther.
␈↓ α←␈↓When␈α⊗we␈α⊗write␈α⊗␈↓αsqrt(x)␈↓␈α⊗in␈α∃Fortran,␈α⊗for␈α⊗example,␈α⊗we␈α⊗are␈α⊗initially␈α∃only
␈↓ α←␈↓concerned␈α≤with␈α≤␈↓αsqrt␈↓␈α≤as␈α≤a␈α≤mathematical␈α≤function␈α≤defined␈α≤such␈α≠that
␈↓ α←␈↓␈↓αx = sqrt(x)*sqrt(x)␈↓.␈α∂We␈α∂are␈α∂not␈α⊂interested␈α∂in␈α∂the␈α∂specific␈α∂algorithm␈α⊂used␈α∂to
␈↓ α←␈↓approximate␈α
the␈α
function␈α∞intended␈α
in␈α
the␈α
notation.␈α∞Indeed,␈α
thought␈α
of␈α∞as␈α
a
␈↓ α←␈↓mathematical␈α⊃notation,␈α⊃it␈α⊂doesn't␈α⊃matter␈α⊃how␈α⊂␈↓αsqrt␈↓␈α⊃is␈α⊃computed.␈α⊃We␈α⊂might
␈↓ α←␈↓wish␈α
to␈α
prove␈α
some␈α
properties␈α
of␈αthe␈α
algorithm␈α
which␈α
we␈α
are␈α
encoding.␈α If␈α
so,
␈↓ α←␈↓we␈α
would␈α
only␈α∞use␈α
the␈α
mathematical␈α
properties␈α∞of␈α
the␈α
idealized␈α∞square␈α
root
␈↓ α←␈↓function.␈α
Only␈α
later,␈α
after␈α
we␈α
had␈α
convinced␈α
ourselves␈α
of␈α
the␈αcorrect␈α
encoding
␈↓ α←␈↓of␈α⊗our␈α⊗intention␈α⊗in␈α⊗the␈α↔Fortran␈α⊗program,␈α⊗would␈α⊗we␈α⊗worry␈α↔about␈α⊗the
␈↓ α←␈↓computational␈α∂aspects␈α∞of␈α∂the␈α∞Fortran␈α∂implementation␈α∞␈↓αsqrt␈↓.␈α∂The␈α∂typical␈α∞user
␈↓ α←␈↓␈↓␈↓ 	2Preface     iii␈↓

␈↓"β␈↓ α←␈↓will␈α∪never␈α∪proceed␈α∪deeper␈α∪into␈α∪the␈α∪representation␈α∪than␈α∪this;␈α∪only␈α∀if␈α∪his
␈↓ α←␈↓computation␈α≠is␈α≤lethargic␈α≠due␈α≠to␈α≤inefficiencies,␈α≠or␈α≠inaccurate␈α≤due␈α≠to
␈↓ α←␈↓uncooperative␈α∞approximations,␈α∞will␈α
he␈α∞look␈α∞at␈α
the␈α∞actual␈α∞implementation␈α
of
␈↓ α←␈↓␈↓αsqrt␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'Just␈αas␈α
it␈αis␈α
unnecessary␈αto␈α
learn␈αmachine␈α
language␈αto␈α
study␈αnumerical
␈↓ α←␈↓algorithms,␈α∂it␈α∞is␈α∂also␈α∂unnecessary␈α∞to␈α∂learn␈α∞machine␈α∂language␈α∂to␈α∞understand
␈↓ α←␈↓non-numerical␈α∂or␈α∂data␈α∂structure␈α∞processes.␈α∂ We␈α∂make␈α∂a␈α∂distinction␈α∞between
␈↓ α←␈↓data␈α⊗structures␈α⊗and␈α↔storage␈α⊗structures.␈α⊗Data␈α⊗structures␈α↔are␈α⊗abstractions,
␈↓ α←␈↓independent␈αof␈α␈↓¬how␈↓␈αthey␈αare␈αimplemented␈αon␈αa␈αmachine.␈α Data␈αstructures␈αare
␈↓ α←␈↓representations␈α_of␈α↔information␈α_chosen␈α↔to␈α_exhibit␈α↔certain␈α_ordering␈α↔and
␈↓ α←␈↓accessibility␈α≤relationships␈α≤between␈α≤data␈α≤items.␈α≤ Storage␈α≤structures␈α≠are
␈↓ α←␈↓particular␈αimplementations␈αof␈αthe␈αabstract␈αideas.␈α Certainly␈αwe␈αcannot␈αignore
␈↓ α←␈↓storage␈αstructures␈αwhen␈αwe␈αare␈α
deciding␈αupon␈αthe␈αdata␈αstructures␈α
which␈αwill
␈↓ α←␈↓encode␈α⊃the␈α⊃algorithm,␈α⊃but␈α⊃the␈α⊃interesting␈α⊃aspects␈α⊃of␈α⊃the␈α∩representation␈α⊃of
␈↓ α←␈↓information␈α
can␈α∞be␈α
discussed␈α∞at␈α
the␈α∞level␈α
of␈α∞data␈α
structures␈α∞with␈α
no␈α∞loss␈α
of
␈↓ α←␈↓generality.␈α∂ The␈α∂mapping␈α∞of␈α∂data␈α∂structures␈α∞to␈α∂storage␈α∂structures␈α∂is␈α∞usually
␈↓ α←␈↓quite␈α∞machine␈α∞dependent␈α∂and␈α∞we␈α∞are␈α∞more␈α∂interested␈α∞in␈α∞ideas␈α∂than␈α∞coding
␈↓ α←␈↓tricks.␈α∞ We␈α∞will␈α∞see␈α∞that␈α∞it␈α∞is␈α∞possible,␈α∞and␈α∞most␈α∞beneficial,␈α∞to␈α∞structure␈α∞our
␈↓ α←␈↓programs␈α∩such␈α∪that␈α∩there␈α∪is␈α∩a␈α∪very␈α∩clean␈α∪interface␈α∩between␈α∪the␈α∩abstract
␈↓ α←␈↓algorithm␈α⊃and␈α⊃the␈α⊃chosen␈α⊃representation.␈α⊃ That␈α⊃is,␈α⊃there␈α⊃will␈α⊃be␈α⊃a␈α⊃set␈α⊃of
␈↓ α←␈↓representation-manipulating␈α∞programs␈α∞to␈α∞test,␈α∞select␈α∞or␈α∞construct␈α∞elements␈α
of
␈↓ α←␈↓the␈αdomain;␈α
and␈αthere␈α
will␈αbe␈αa␈α
program␈αencoding␈α
the␈αalgorithm.␈αChanges␈α
of
␈↓ α←␈↓representations␈α∃only␈α∃require␈α∃changes␈α∃to␈α∃the␈α∃programs␈α∃which␈α⊗access␈α∃the
␈↓ α←␈↓representation, not to the basic program.
␈↓"β␈↓ α←␈↓␈↓ β'One␈αimportant␈αinsight␈αwhich␈αshould␈αbe␈αcultivated␈αin␈αthis␈αprocess␈αis␈αthe
␈↓ α←␈↓distinction␈α⊃between␈α⊃the␈α⊃concepts␈α⊃of␈α⊂function␈α⊃and␈α⊃algorithm.␈α⊃ The␈α⊃idea␈α⊂of
␈↓ α←␈↓function␈α∞is␈α∞mathematical␈α
and␈α∞is␈α∞independent␈α
of␈α∞any␈α∞notion␈α∞of␈α
computation;
␈↓ α←␈↓the␈α
meaning␈αof␈α
"algorithm"␈α
is␈αcomputational,␈α
the␈α
effect␈αof␈α
an␈αalgorithm␈α
being
␈↓ α←␈↓to␈α
compute␈αa␈α
function.␈α
Thus␈αthere␈α
are␈α
typically␈αmany␈α
algorithms␈α
which␈αwill
␈↓ α←␈↓compute a specific function.
␈↓"β␈↓ α←␈↓␈↓ β'This␈α⊃text␈α⊃is␈α⊃␈↓¬not␈↓␈α⊃meant␈α⊃to␈α⊃be␈α⊃a␈α⊃programming␈α⊃manual␈α⊃for␈α⊃LISP.␈α⊃ A
␈↓ α←␈↓certain␈α∞amount␈α∂of␈α∞time␈α∂is␈α∞spent␈α∂giving␈α∞insights␈α∂into␈α∞techniques␈α∂for␈α∞writing
␈↓ α←␈↓LISP␈α⊃functions.␈α⊃ There␈α⊃are␈α⊃two␈α⊃reasons␈α⊃for␈α⊃this.␈α⊃First,␈α⊃the␈α⊃style␈α⊃of␈α⊂LISP
␈↓ α←␈↓programming␈α∞is␈α∞quite␈α∞different␈α∞from␈α∞that␈α∞of␈α∞"normal"␈α∞programming.␈α
 LISP
␈↓ α←␈↓was␈α~one␈α≠of␈α~the␈α~first␈α≠languages␈α~to␈α~exploit␈α≠the␈α~virtues␈α≠of␈α~recursive
␈↓ α←␈↓programming␈αand␈αexplore␈αthe␈αpower␈αof␈αprocedure-valued␈αvariables.␈α Second,
␈↓ α←␈↓we␈α
will␈α
spend␈α
a␈α
great␈α
deal␈α
of␈α
time␈α
discussing␈α
various␈α
levels␈α
of␈α
implementation
␈↓ α←␈↓of␈α∪the␈α∪language.␈α∩LISP␈α∪is␈α∪an␈α∩excellent␈α∪medium␈α∪for␈α∪introducing␈α∩standard
␈↓ α←␈↓techniques␈αin␈αdata␈αstructure␈αmanipulation.␈αTechniques␈αfor␈αimplementation␈α
of
␈↓ α←␈↓recursion,␈α⊂implementation␈α⊂of␈α∂complex␈α⊂data␈α⊂structures,␈α⊂storage␈α∂management,
␈↓ α←␈↓and␈α∃symbol␈α⊗table␈α∃manipulation␈α⊗are␈α∃easily␈α∃motivated␈α⊗in␈α∃the␈α⊗context␈α∃of
␈↓ α←␈↓language␈α∞implementation.␈α∂Many␈α∞of␈α∂these␈α∞standard␈α∂techniques␈α∞first␈α∂arose␈α∞in
␈↓ α←␈↓the␈α∂implementation␈α∂of␈α⊂LISP.␈α∂But␈α∂it␈α∂is␈α⊂pointless␈α∂to␈α∂attempt␈α∂a␈α⊂discussion␈α∂of
␈↓ α←␈↓implementation unless the reader has a thorough grasp of the language.
␈↓ α←␈↓␈↓iv  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓␈↓ β'Granting␈αthe␈αefficacy␈αof␈αour␈αendeavor␈αin␈αabstraction,␈αwhy␈αstudy␈αLISP?
␈↓ α←␈↓LISP␈α∪is␈α∀at␈α∪least␈α∀fifteen␈α∪years␈α∪old␈α∀and␈α∪many␈α∀new␈α∪languages␈α∀have␈α∪been
␈↓ α←␈↓proposed.␈α∃ The␈α⊗difficulty␈α∃is␈α⊗that␈α∃the␈α⊗appropriate␈α∃combination␈α⊗of␈α∃these
␈↓ α←␈↓features␈α
is␈α
not␈α
present␈α
in␈α
any␈α
other␈α
language.␈α
LISP␈α
unifies␈α∞and␈α
rationalizes
␈↓ α←␈↓many␈α
divergent␈α
formulations␈α
of␈αlanguage␈α
constructs.␈α
 One␈α
might␈αsurmise␈α
that
␈↓ α←␈↓a␈α∩new␈α∪language,␈α∩profiting␈α∪from␈α∩LISP's␈α∩experience,␈α∪would␈α∩make␈α∪a␈α∩better
␈↓ α←␈↓pedagogical␈α
tool.␈α A␈α
strong␈αsuccessor␈α
has␈αnot␈α
arrived,␈αand␈α
toy␈α
languages␈αare
␈↓ α←␈↓suspect␈αfor␈αseveral␈αreasons.␈αThe␈αstudent␈αmay␈αsuspect␈αthat␈αhe␈αis␈αa␈αsubject␈αin␈α
a
␈↓ α←␈↓not␈α∪too␈α∪clever␈α∪experiment␈α∪being␈α∪performed␈α∪upon␈α∪him␈α∪by␈α∪his␈α∩instructor.
␈↓ α←␈↓Having␈α∩a␈α∪backlog␈α∩of␈α∪fifteen␈α∩years␈α∩of␈α∪experience␈α∩and␈α∪example␈α∩programs
␈↓ α←␈↓should␈αdo␈αmuch␈αto␈αalleviate␈αthis␈αdiscomfort.␈α The␈αdevelopment␈αof␈αLISP␈αalso
␈↓ α←␈↓shows␈α⊂many␈α⊂of␈α⊂the␈α⊂mistakes␈α∂that␈α⊂the␈α⊂original␈α⊂implementors␈α⊂and␈α∂designers
␈↓ α←␈↓made.␈α
 We␈α
will␈α
point␈α
out␈α
the␈α
flaws␈α
and␈α
pitfalls␈α
awaiting␈α
the␈αunwary␈α
language
␈↓ α←␈↓designer.
␈↓"β␈↓ α←␈↓␈↓ β'We␈αclaim␈α
the␈αmore␈αinteresting␈α
aspects␈αof␈αLISP␈α
for␈αstudents␈αof␈α
computer
␈↓ α←␈↓science␈αlie␈αnot␈αin␈αits␈αfeatures␈αas␈αa␈αprogramming␈αlanguage,␈αbut␈αin␈αwhat␈αit␈αcan
␈↓ α←␈↓show␈αabout␈αthe␈α␈↓¬structure␈↓␈αof␈αcomputer␈αscience.␈α There␈αis␈αa␈αrapidly␈αexpanding
␈↓ α←␈↓body␈α⊃of␈α⊃knowledge␈α⊃unique␈α⊃to␈α⊃computer␈α⊃science,␈α⊃neither␈α⊃mathematical␈α⊂nor
␈↓ α←␈↓engineering␈αper␈α
se.␈α Much␈α
of␈αthis␈αarea␈α
is␈αpresented␈α
most␈αclearly␈α
by␈αstudying
␈↓ α←␈↓LISP.
␈↓"β␈↓ α←␈↓␈↓ β'Again␈α∪there␈α∪are␈α∪two␈α∪ways␈α∪to␈α∪look␈α∪at␈α∪a␈α∪high␈α∪level␈α∪language:␈α∪as␈α∪a
␈↓ α←␈↓mathematical␈α
formalism,␈α
and␈α
as␈α
a␈α
programming␈α
language.␈α
 LISP␈α
is␈α
a␈α
better
␈↓ α←␈↓formalism␈α⊂than␈α⊂most␈α⊂of␈α⊂its␈α⊂mathematical␈α⊂rivals␈α⊂because␈α⊂there␈α⊃is␈α⊂sufficient
␈↓ α←␈↓organizational␈α
complexity␈α
present␈αin␈α
LISP␈α
so␈α
as␈αto␈α
make␈α
its␈αimplementation␈α
a
␈↓ α←␈↓realistic␈α∀computer␈α∀science␈α∀task␈α∪and␈α∀not␈α∀just␈α∀an␈α∀interesting␈α∪mathematical
␈↓ α←␈↓curiosity.␈α∪ Much␈α∪of␈α∪the␈α∪power␈α∪of␈α∩LISP␈α∪lies␈α∪in␈α∪its␈α∪simplicity.␈α∪ The␈α∩data
␈↓ α←␈↓structures␈αare␈αrich␈αenough␈αto␈αeasily␈αdescribe␈αsophisticated␈αalgorithms␈αbut␈αnot
␈↓ α←␈↓so␈α
rich␈α
as␈α
to␈α
become␈αobfuscatory.␈α
 Most␈α
every␈α
aspect␈α
of␈α
the␈αimplementation␈α
of
␈↓ α←␈↓LISP␈αand␈αits␈α
translators␈αhas␈αimmediate␈α
implications␈αto␈αthe␈αimplementation␈α
of
␈↓ α←␈↓other languages and to the design of programming languages in general.
␈↓"β␈↓ α←␈↓␈↓ β'We␈α⊃will␈α⊂describe␈α⊃language␈α⊂translators␈α⊃(interpreters␈α⊂and␈α⊃compilers)␈α⊂as
␈↓ α←␈↓LISP␈α∂functions.␈α∂ The␈α∂structure␈α∂of␈α∂these␈α∂translators␈α∂when␈α∂exposed␈α∂as␈α∂LISP
␈↓ α←␈↓functions␈α⊂aids␈α⊂immensely␈α⊂in␈α⊂understanding␈α⊂the␈α⊂essential␈α⊂character␈α⊃of␈α⊂such
␈↓ α←␈↓translators.␈α This␈αis␈αpartly␈αdue␈αto␈αthe␈αsimplicity␈αof␈αthe␈αlanguage,␈αbut␈αperhaps
␈↓ α←␈↓more␈α⊃due␈α⊂to␈α⊃our␈α⊂ability␈α⊃to␈α⊃go␈α⊂right␈α⊃to␈α⊂the␈α⊃essential␈α⊃translating␈α⊂algorithm
␈↓ α←␈↓without becoming bogged down in details of syntax.
␈↓"β␈↓ α←␈↓␈↓ β'LISP␈α∩has␈α∩very␈α∩important␈α∩implications␈α∩in␈α∩the␈α∩field␈α∩of␈α⊃programming
␈↓ α←␈↓language␈αsemantics,␈α
and␈αis␈αthe␈α
dominant␈αlanguage␈αin␈α
the␈αclosely␈αrelated␈α
study
␈↓ α←␈↓of␈αprovability␈αof␈αproperties␈αof␈αprograms.␈α The␈αidea␈αof␈αproving␈α
properties␈αof
␈↓ α←␈↓programs␈α⊗has␈α⊗been␈α⊗around␈α⊗for␈α↔a␈α⊗very␈α⊗long␈α⊗time.␈α⊗Goldstein␈α↔and␈α⊗von
␈↓ α←␈↓Neumann␈α↔were␈α↔aware␈α↔of␈α↔the␈α↔practical␈α↔benefits␈α↔of␈α↔such␈α↔endeavors.␈α↔J.
␈↓ α←␈↓McCarthy's␈α∃work␈α⊗in␈α∃LISP␈α⊗and␈α∃the␈α∃Theory␈α⊗of␈α∃Computation␈α⊗sought␈α∃to
␈↓ α←␈↓establish␈α⊂formalisms␈α⊂and␈α⊂rules␈α∂of␈α⊂inference␈α⊂for␈α⊂reasoning␈α⊂about␈α∂programs.
␈↓ α←␈↓However,␈α∂the␈α∂working␈α∂programmers␈α∞recognized␈α∂debugging␈α∂as␈α∂the␈α∂only␈α∞tool
␈↓ α←␈↓␈↓␈↓ 	<Preface     v␈↓

␈↓"β␈↓ α←␈↓with␈α which␈α to␈α generate␈α!a␈α "correct"␈α program,␈α though␈α!clearly␈α the
␈↓ α←␈↓non-occurrence␈α∂of␈α∂bugs␈α∂is␈α∂no␈α∂guarantee␈α∂of␈α∂correctness.␈α∂ Until␈α⊂very␈α∂recently
␈↓ α←␈↓techniques␈α∞for␈α
establishing␈α∞correctness␈α
of␈α∞practical␈α
programs␈α∞simply␈α∞did␈α
not
␈↓ α←␈↓exist.
␈↓"β␈↓ α←␈↓␈↓ β'A recent set of events is beginning to change this.

␈↓"λ␈↓ α←␈↓␈↓↓1.␈↓␈α
Programs␈α
are␈αbecoming␈α
so␈α
large␈αand␈α
complex␈α
that,␈αeven␈α
though␈α
we␈αwrite
␈↓ α←␈↓␈↓ β∂in␈α∂a␈α∂high-level␈α∂language,␈α∂our␈α∞intuitions␈α∂are␈α∂not␈α∂sufficient␈α∂to␈α∂sustain␈α∞us
␈↓ α←␈↓␈↓ β∂when␈α∞we␈α
try␈α∞to␈α
find␈α∞bugs.␈α
We␈α∞are␈α
literally␈α∞being␈α
forced␈α∞to␈α∞look␈α
beyond
␈↓ α←␈↓␈↓ β∂debugging.
␈↓"	␈↓ α←␈↓␈↓↓2.␈↓␈α∂The␈α∞formalisms␈α∂are␈α∂maturing.␈α∞We␈α∂know␈α∞a␈α∂lot␈α∂more␈α∞about␈α∂how␈α∂to␈α∞write
␈↓ α←␈↓␈↓ β∂"structured␈α
programs";␈α
we␈α
know␈α
how␈α
to␈α
design␈α
languages␈α
whose␈α
constructs
␈↓ α←␈↓␈↓ β∂are␈αmore␈αamenable␈αto␈αproof␈αtechniques.␈α And␈αmost␈αimportantly,␈αthe␈αtools
␈↓ α←␈↓␈↓ β∂we␈α→need␈α→for␈α→expressing␈α→properties␈α→of␈α→programs␈α→are␈α→finally␈α→being
␈↓ α←␈↓␈↓ β∂developed.
␈↓"	␈↓ α←␈↓␈↓↓3.␈↓␈α∀The␈α∀development␈α∀of␈α∀on-line␈α∪techniques.␈α∀The␈α∀on-line␈α∀system,␈α∀with␈α∪its
␈↓ α←␈↓␈↓ β∂sophisticated␈α∩display␈α∩editors,␈α∩debuggers␈α∩and␈α∩file␈α∩handlers,␈α∩is␈α∩the␈α⊃only
␈↓ α←␈↓␈↓ β∂reason␈α⊃that␈α⊃the␈α⊃traditional␈α⊃means␈α⊃of␈α⊃construction␈α⊃and␈α⊃modification␈α⊃of
␈↓ α←␈↓␈↓ β∂complex␈α∞programs␈α∞and␈α∞systems␈α∞has␈α
been␈α∞able␈α∞to␈α∞survive␈α∞this␈α∞long.␈α
The
␈↓ α←␈↓␈↓ β∂interactive␈α∪experience␈α∪can␈α∪now␈α∩be␈α∪adapted␈α∪to␈α∪program␈α∪verifiers␈α∩and
␈↓ α←␈↓␈↓ β∂synthesizers.

␈↓"β␈↓ α←␈↓␈↓ β'This␈α∪view␈α∩of␈α∪the␈α∩programming␈α∪process␈α∩blends␈α∪well␈α∩with␈α∪the␈α∩LISP
␈↓ α←␈↓philosophy.␈α
 We␈αwill␈α
show␈αthat␈α
the␈α
most␈αnatural␈α
way␈αto␈α
write␈αLISP␈α
programs
␈↓ α←␈↓is␈α"structured"␈αin␈αthe␈αbest␈αsense␈αof␈αthe␈αword,␈αbeing␈αclean␈αin␈αcontrol␈αstructure,
␈↓ α←␈↓concise␈α∞by␈α
not␈α∞attempting␈α
to␈α∞do␈α∞too␈α
much,␈α∞and␈α
independent␈α∞of␈α∞a␈α
particular
␈↓ α←␈↓data representation.
␈↓"β␈↓ α←␈↓␈↓ β'Many␈α
of␈αthe␈α
existing␈α
techniques␈αfor␈α
establishing␈α
correctness␈αoriginated
␈↓ α←␈↓in␈α⊗McCarthy's␈α⊗investigations␈α⊗of␈α⊗LISP;␈α∃and␈α⊗some␈α⊗very␈α⊗recent␈α⊗work␈α∃on
␈↓ α←␈↓mathematical␈α
models␈α
for␈α
programming␈αlanguages␈α
is␈α
easily␈α
motivated␈α
from␈αa
␈↓ α←␈↓discussion of LISP.
␈↓"β␈↓ α←␈↓␈↓ β'LISP␈αis␈αthe␈αstarting␈α
point␈αfor␈αthose␈αinterested␈αin␈α
Artificial␈αIntelligence.
␈↓ α←␈↓It␈α∃is␈α∃no␈α∃longer␈α∃the␈α∃"research"␈α∃language,␈α∃but␈α∃has␈α∃become␈α∃the␈α∃"systems"
␈↓ α←␈↓language␈αfor␈αA.I.␈αToday's␈αresearch␈αlanguages␈αare␈αbuilt␈αon␈αLISP,␈αusing␈αLISP
␈↓ α←␈↓as a machine language.
␈↓"β␈↓ α←␈↓␈↓ β'Finally␈αthere␈αare␈αcertain␈αproperties␈αof␈αLISP-like␈αlanguages␈αwhich␈αmake
␈↓ α←␈↓them␈α∩the␈α∩natural␈α∩candidate␈α∩for␈α∩interactive␈α∩program␈α∩specification.␈α∩ In␈α⊃the
␈↓ α←␈↓chapter␈α∞on␈α∞implications␈α∞of␈α∞LISP␈α∞we␈α∞will␈α∞characterize␈α∞"LISP-like"␈α∞and␈α
show
␈↓ α←␈↓how interactive methods can be developed.
␈↓"β␈↓ α←␈↓␈↓ β'This␈α⊂text␈α∂is␈α⊂primarily␈α∂designed␈α⊂for␈α∂undergraduates␈α⊂and␈α⊂therefore␈α∂an
␈↓ α←␈↓attempt␈α
is␈α∞made␈α
to␈α∞make␈α
it␈α
self-contained.␈α∞There␈α
are␈α∞basically␈α
five␈α∞areas␈α
in
␈↓ α←␈↓which␈α
to␈α
partition␈α
the␈α
topics:␈α
the␈α
mechanics␈α
of␈α
the␈α
language,␈α
the␈αevaluation
␈↓ α←␈↓of␈αexpressions␈αin␈αLISP,␈αthe␈αstatic␈αstructure␈αof␈αLISP,␈αthe␈αdynamic␈αstructure␈αof
␈↓ α←␈↓␈↓vi  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓LISP,␈α∩and␈α∩the␈α∩efficient␈α∩representation␈α∩of␈α∩data␈α∩structures␈α∪and␈α∩algorithms.
␈↓ α←␈↓Each␈α
area␈α∞builds␈α
on␈α∞the␈α
previous.␈α
Taken␈α∞as␈α
a␈α∞group␈α
these␈α∞topics␈α
introduce
␈↓ α←␈↓much of what is interesting computer science.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α
first␈αarea␈α
develops␈α
the␈αprogramming␈α
philosophy␈αof␈α
LISP:␈α
the␈αuse
␈↓ α←␈↓of␈α∂data␈α∂structures␈α∞in␈α∂programming;␈α∂the␈α∞language␈α∂primitives,␈α∂recursion,␈α∞and
␈↓ α←␈↓other␈α∞control␈α∞structures.␈α∞ The␈α∞second␈α∞area,␈α∞involving␈α∞a␈α∞careful␈α∞study␈α∞of␈α
the
␈↓ α←␈↓meaning␈α∞of␈α∞evaluation␈α∂in␈α∞LISP,␈α∞gives␈α∞insights␈α∂into␈α∞other␈α∞languages␈α∂and␈α∞to
␈↓ α←␈↓the␈α⊂general␈α⊂question␈α⊂of␈α⊃implementation.␈α⊂The␈α⊂next␈α⊂two␈α⊂areas␈α⊃are␈α⊂involved
␈↓ α←␈↓with␈α⊃implementation.␈α⊃The␈α⊃section␈α∩on␈α⊃static␈α⊃structure␈α⊃deals␈α⊃with␈α∩the␈α⊃basic
␈↓ α←␈↓organization␈α
of␈α
memory␈α
for␈α
a␈α
LISP␈α
machine -- be␈α
it␈α
hardware␈α∞or␈α
simulated
␈↓ α←␈↓in␈αsoftware.␈αThe␈αdynamics␈αof␈αLISP␈αdiscusses␈αthe␈αprimitive␈αcontrol␈αstructures
␈↓ α←␈↓necessary␈α∂for␈α∞implementation␈α∂of␈α∞the␈α∂LISP␈α∞control␈α∂structures␈α∂and␈α∞procedure
␈↓ α←␈↓calls.␈α∀LISP␈α∃compilers␈α∀are␈α∃discussed␈α∀here.␈α∀ The␈α∃final␈α∀section␈α∃relates␈α∀our
␈↓ α←␈↓discussion␈α
of␈αLISP␈α
and␈α
its␈αimplementation␈α
to␈α
the␈αmore␈α
traditional␈αmaterial␈α
of
␈↓ α←␈↓a␈α
data␈α
structures␈αcourse.␈α
We␈α
discuss␈αthe␈α
problems␈α
of␈α
efficient␈αrepresentation
␈↓ α←␈↓of␈α→data␈α→structures.␈α→By␈α→this␈α~point␈α→the␈α→student␈α→should␈α→have␈α~a␈α→better
␈↓ α←␈↓understanding␈α⊃of␈α⊂the␈α⊃uses␈α⊂of␈α⊃data␈α⊂structures␈α⊃and␈α⊂should␈α⊃be␈α⊃motivated␈α⊂to
␈↓ α←␈↓examine these issues with a better understanding.
␈↓"β␈↓ α←␈↓␈↓ β'A␈α
large␈αcollection␈α
of␈αproblems␈α
has␈αbeen␈α
included.␈αThe␈α
reader␈α
is␈αurged
␈↓ α←␈↓to␈αdo␈αas␈α
many␈αas␈αpossible.␈α
 The␈αproblems␈αare␈α
mostly␈αnon-trivial;␈αthey␈α
attempt
␈↓ α←␈↓to␈α∞be␈α∞realistic,␈α
introducing␈α∞some␈α∞new␈α
information␈α∞which␈α∞the␈α∞readers␈α
should
␈↓ α←␈↓be␈α∪able␈α∪to␈α∪discover␈α∪themselves.␈α∩There␈α∪are␈α∪also␈α∪a␈α∪few␈α∪rather␈α∩substantial
␈↓ α←␈↓projects.␈α At␈αleast␈αone␈αshould␈αbe␈αattempted.␈α There␈αis␈αa␈αsignificant␈αdifference
␈↓ α←␈↓between␈α⊂being␈α⊂able␈α⊃to␈α⊂program␈α⊂small␈α⊂problems␈α⊃and␈α⊂being␈α⊂able␈α⊃to␈α⊂handle
␈↓ α←␈↓large␈α∞projects.␈α
Small␈α∞programming␈α∞projects␈α
can␈α∞be␈α
accomplished␈α∞in␈α∞spite␈α
of
␈↓ α←␈↓any␈α⊃admonitions␈α⊃about␈α∩"good␈α⊃programming␈α⊃style".␈α∩ A␈α⊃large␈α⊃project␈α∩is␈α⊃an
␈↓ α←␈↓effective␈α∩demonstration␈α∩of␈α∪the␈α∩need␈α∩for␈α∩elegant␈α∪programming␈α∩techniques.
␈↓ α←␈↓The␈α∃text␈α∃is␈α∃large␈α∃and␈α∃covers␈α∀much␈α∃more␈α∃than␈α∃is␈α∃recommended␈α∃for␈α∀a
␈↓ α←␈↓one-semester course. A typical one semester course on data structures covers:
␈↓"∀␈↓ α←␈↓␈↓ βWChapter 1: all
␈↓"	␈↓ α←␈↓␈↓ βWChapter 2: without 2.4, 2.5, and 2.10.
␈↓"	␈↓ α←␈↓␈↓ βWChapter 3: without the mathematical aspects of 3.13
␈↓"	␈↓ α←␈↓␈↓ βWChapter 4: without 4.7, 4.8, and the mathematical aspects of 4.11
␈↓"	␈↓ α←␈↓␈↓ βWChapter 5: without 5.8, 5.19, and 5.20
␈↓"	␈↓ α←␈↓␈↓ βWChapter 6: without 6.8,  and 6.12 through 6.20
␈↓"	␈↓ α←␈↓␈↓ βWChapter 7: without 7.5, 7.6,  and 7.10 through 7.14
␈↓"	␈↓ α←␈↓␈↓ βWChapter 8 is also optional.
␈↓"∀␈↓ α←␈↓␈↓ β'If␈α∞a␈α∞good␈α∞interactive␈α∞LISP␈α
implementation␈α∞is␈α∞available,␈α∞then␈α∞the␈α
pace
␈↓ α←␈↓can␈α⊂be␈α⊂quickened␈α⊂and␈α⊂the␈α⊂projects␈α⊂enlarged.␈α⊂ However,␈α⊂if␈α⊂only␈α⊂a␈α⊂poor␈α∂or
␈↓ α←␈↓mediocre␈α⊂implementation␈α∂is␈α⊂accessible,␈α∂then␈α⊂the␈α∂course␈α⊂time␈α∂is␈α⊂better␈α∂spent
␈↓ α←␈↓without␈α∩␈↓¬any␈↓␈α∩actual␈α∩programming,␈α∩or␈α∩the␈α∩course␈α∩should␈α∩be␈α∪augmented␈α∩to
␈↓ α←␈↓include␈α∀an␈α∀implementation␈α∀laboratory.␈α∀ LISP␈α∀is␈α∀an␈α∀interactive␈α∀language;
␈↓ α←␈↓␈↓␈↓ 	*Preface     vii␈↓

␈↓"β␈↓ α←␈↓attempts␈α∞at␈α∂other␈α∞modes␈α∂of␈α∞operation␈α∞do␈α∂a␈α∞disservice␈α∂to␈α∞both␈α∂the␈α∞language
␈↓ α←␈↓and the user.
␈↓"β␈↓ α←␈↓␈↓ β'Finally␈α
a␈α
note␈αon␈α
the␈α
structure␈αof␈α
the␈α
text.␈αThe␈α
emphasis␈α
flows␈αfrom␈α
the
␈↓ α←␈↓abstract␈αto␈αthe␈αspecific,␈αbeginning␈αwith␈αa␈αdescription␈αof␈αthe␈αdomain␈α
of␈αLISP
␈↓ α←␈↓functions␈α⊃and␈α∩the␈α⊃operations␈α∩defined␈α⊃over␈α∩that␈α⊃domain,␈α∩and␈α⊃moves␈α∩to␈α⊃a
␈↓ α←␈↓discussion␈α
of␈α∞the␈α
details␈α∞of␈α
efficient␈α∞implementation␈α
of␈α∞LISP-like␈α
languages.
␈↓ α←␈↓The␈α∀practical-minded␈α∀programmer␈α∪might␈α∀be␈α∀put␈α∪off␈α∀by␈α∀the␈α∪"irrelevant"
␈↓ α←␈↓theory␈α∂and␈α⊂the␈α∂theoretical-minded␈α⊂mathematician␈α∂might␈α∂be␈α⊂put␈α∂off␈α⊂by␈α∂the
␈↓ α←␈↓"irrelevant"␈α⊂details␈α⊂of␈α⊂implementation.␈α⊂If␈α⊂you␈α⊂lie␈α⊂somewhere␈α⊂between␈α∂these
␈↓ α←␈↓two extremes, then welcome.
␈↓ α←␈↓␈↓4  CONTENTS␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓↓␈↓ ∧aT A B L E   O F   C O N T E N T S



␈↓ α←␈↓↓PREFACE␈↓ 
Ei

␈↓ α←␈↓↓CHAPTER␈↓ 	|PAGE␈↓

␈↓ α←␈↓␈↓ βc.1␈↓ ∧+Symbolic Expressions: Abstract Data Structures␈↓ λ← .  .  .  .  .  .  .  . ␈↓ 
6 1


␈↓ α←␈↓␈↓↓INDEX␈↓ 
A3␈↓

␈↓ α←␈↓␈↓ β'TEXT
␈↓ α←␈↓␈↓.1␈↓ ¬USymbolic Expressions: Abstract Data Structures     1␈↓

␈↓"β␈↓ α←␈↓␈↓ ∧␈↓↓.1  Symbolic Expressions: Abstract Data Structures␈↓

␈↓"β␈↓ α←␈↓We␈α∞wish␈α∞to␈α
show␈α∞that␈α∞the␈α∞use␈α
of␈α∞abstraction␈α∞will␈α
benefit␈α∞the␈α∞study␈α∞of␈α
data
␈↓ α←␈↓structures␈α∞and␈α∞LISP.␈α∞ To␈α∂begin␈α∞our␈α∞study␈α∞we␈α∞should␈α∂therefore␈α∞characterize
␈↓ α←␈↓the␈αdomain␈αof␈αLISP␈αdata␈αstructures␈αin␈αa␈αmanner␈αsimilar␈αto␈αwhat␈αwe␈α
did␈αfor
␈↓ α←␈↓numbers.
␈↓"β␈↓ α←␈↓␈↓ β'Our␈α→objects␈α→are␈α→called␈α→␈↓↓Symbolic␈α→Expressions␈↓.␈α→ Our␈α→domain␈α→of
␈↓ α←␈↓Symbolic␈α∩Expressions␈α∩is␈α∩named␈α∩␈↓<sexpr>␈↓.␈α∩ Symbolic␈α∩expressions␈α∩are␈α⊃also
␈↓ α←␈↓known as ␈↓↓S-expressions␈↓ or ␈↓↓S-exprs␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α
set␈α∞of␈α
symbolic␈α
expressions␈α∞is␈α
defined␈α
inductively␈α∞over␈α
a␈α∞base␈α
set
␈↓ α←␈↓named␈α
␈↓<atom>␈↓.␈α
The␈α
set␈α
␈↓<atom>␈↓␈α
can␈α
itself␈α
be␈α
defined␈α
inductively.␈α
We␈α
give␈α
a
␈↓ α←␈↓set␈α∃of␈α∀BNF␈α∃equations␈α∀for␈α∃elements␈α∀of␈α∃<atom>␈α∀below,␈α∃but␈α∃the␈α∀essential
␈↓ α←␈↓character␈αof␈αthe␈αdomain␈αis␈αthat␈αit␈αrepresents␈αtwo␈αkinds␈αof␈αobjects:␈αthe␈α␈↓↓literal
␈↓ α←␈↓↓atoms␈↓ and the integers.  The elements of ␈↓<atom>␈↓ are called ␈↓↓atoms␈↓.
␈↓"∀␈↓ α←␈↓<atom>␈↓ ∧7:: = <literal atom> | <numeral> | -<numeral>
␈↓"	␈↓ α←␈↓<literal atom>␈↓ ∧7:: = <atom letter>
␈↓"β␈↓ α←␈↓␈↓ ∧7:: = <literal atom><atom letter>
␈↓"β␈↓ α←␈↓␈↓ ∧7:: = <literal atom><digit>
␈↓"	␈↓ α←␈↓<numeral>␈↓ ∧7:: = <digit> | <numeral><digit>
␈↓"	␈↓ α←␈↓<atom letter>␈↓ ∧7:: =␈↓α A | B | C ... | Z␈↓ ␈↓π 1␈↓
␈↓"	␈↓ α←␈↓<digit>␈↓ ∧7:: = ␈↓α0 | 1 | 2 ... | 9␈↓
␈↓"∀␈↓ α←␈↓A␈α<literal␈α
atom>␈αis␈αtherefore␈α
a␈αstring␈αof␈α
uppercase␈αletters␈αand␈α
digits,␈αsubject
␈↓ α←␈↓to the provision that the ␈↓¬first␈↓ character in the atom be a letter.
␈↓"∀␈↓ α←␈↓For example:␈↓ ∧Catoms␈↓ ¬wnon atoms
␈↓"∀␈↓ α←␈↓␈↓α␈↓ ∧CABC123␈↓ ¬w2A
␈↓"	␈↓ α←␈↓α␈↓ ∧C12␈↓ ¬wa
␈↓"	␈↓ α←␈↓α␈↓ ∧CA4D6␈↓ ¬w$$g
␈↓"	␈↓ α←␈↓α␈↓ ∧CNIL␈↓ ¬wABD.
␈↓"	␈↓ α←␈↓α␈↓ ∧CT␈↓ ¬w(A . B)
␈↓"∀␈↓ α←␈↓␈↓ β'The␈α≠characteristics␈α≠of␈α≠atoms␈α≠which␈α≠most␈α≠interest␈α≠us␈α≤are␈α≠their
␈↓ α←␈↓distinguishability:␈α
the␈αatom␈α
␈↓αABC␈↓␈α
is␈αdistinguishable␈α
from␈αthe␈α
atom␈α
␈↓αAB␈↓.␈αThat
␈↓ α←␈↓␈↓α"AB"␈↓␈αis␈αa␈α
part␈αof␈α␈↓α"ABC"␈↓␈α
is␈αnot␈αgermane␈α
to␈αour␈αcurrent␈αdiscussion.␈↓π 2␈↓␈α
Similarly,
␈↓ α←␈↓we␈α⊗will␈α⊗seldom␈α⊗need␈α⊗to␈α⊗exploit␈α⊗numerical␈α⊗relationships␈α⊗underlying␈α⊗the
␈↓ α←␈↓numerals;␈αat␈αmost␈αwe␈αwill␈αuse␈αsimple␈αcounting␈αproperties.␈α Therefore␈αmost␈αof
␈↓ α←␈↓our␈α
discussions␈α
will␈α
deal␈α
with␈α
non-numeric␈α
atoms.␈α
 Most␈α
implementations␈αof
␈↓ α←␈↓LISP␈α#do␈α#however␈α#contain␈α#a␈α#large␈α#arithmetic␈α#entourage.␈α# Many

␈↓"β␈↓ α←␈↓________________
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 1␈↓We use ellipses here as a convenient abbreviation.
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 2␈↓However,␈α≥we␈α≥will␈α≥discuss␈α≥such␈α≥topics␈α≥in␈α≥Section ␈α≥on␈α≥string
␈↓ α←␈↓processing.
␈↓ α←␈↓␈↓2  ␈↓ 
8.1␈↓

␈↓"β␈↓ α←␈↓implementations␈α
also␈αgive␈α
a␈αwider␈α
class␈αof␈α
literal␈αatoms,␈α
allowing␈αsome␈α
special
␈↓ α←␈↓characters␈α⊃to␈α⊃appear;␈α⊃for␈α⊃most␈α⊃of␈α⊃our␈α⊃discussion␈α⊃the␈α⊃above␈α⊃class␈α∩is␈α⊃quite
␈↓ α←␈↓sufficient.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α⊗domain␈α⊗of␈α↔Symbolic␈α⊗expressions,␈α⊗called␈α⊗␈↓<sexpr>␈↓␈α↔is␈α⊗defined
␈↓ α←␈↓inductively over the domain ␈↓<atom>␈↓.␈↓π 3␈↓

␈↓"λ␈↓ α←␈↓␈↓↓1.␈↓  Any element of ␈↓<atom>␈↓ is an element of ␈↓<sexpr>␈↓.
␈↓"	␈↓ α←␈↓␈↓↓2.␈↓  If␈α␈↓λα␈↓β1␈↓␈αand␈α␈↓λα␈↓β2␈↓␈αare␈αelements␈αof␈α
␈↓<sexpr>␈↓,␈αthen␈αthe␈αpair␈αof␈α␈↓λα␈↓β1␈↓␈αand␈α␈↓λα␈↓β2␈↓␈α
is␈αin
␈↓ α←␈↓␈↓ β∂␈↓<sexpr>␈↓.␈α~Pairs␈α~are␈α~also␈α~called␈α~␈↓↓dotted-pairs␈↓␈α~since␈α~their␈α~standard
␈↓ α←␈↓␈↓ β∂representation in LISP is ␈↓α(␈↓λα␈↓β1␈↓α.␈↓λα␈↓β2␈↓α)␈↓.

␈↓"β␈↓ α←␈↓Thus␈α␈↓<sexpr>␈↓␈αincludes␈α␈↓<atom>␈↓␈αas␈αa␈αproper␈αsubset.␈αThe␈αnotation␈αwe␈αchose
␈↓ α←␈↓for the dotted-pairs is the following:
␈↓"∀␈↓ α←␈↓␈↓ βWA␈α
dotted-pair␈αconsists␈α
of␈αa␈α
left-parenthesis␈αfollowed␈α
by␈αan
␈↓ α←␈↓␈↓ βWS-expr,␈α⊗followed␈α∃by␈α⊗a␈α∃period,␈α⊗followed␈α∃by␈α⊗an␈α∃S-expr,
␈↓ α←␈↓␈↓ βWfollowed by a right-parenthesis.
␈↓"∀␈↓ α←␈↓For␈α_example,␈α_let␈α_␈↓λα␈↓β1␈↓␈α↔be␈α_␈↓α(A . B)␈↓␈α_and␈α_␈↓λα␈↓β2␈↓␈α↔be␈α_␈↓α(1 . T)␈↓;␈α_then␈α_␈↓α(␈↓λα␈↓β1␈↓ . ␈↓λα␈↓β2␈↓)␈α↔is
␈↓ α←␈↓␈↓α((A . B) . (1 . T))␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'Greek␈α⊂letters␈α⊃␈↓λα␈↓␈α⊂and␈α⊃␈↓λβ␈↓␈α⊂will␈α⊃be␈α⊂used␈α⊃in␈α⊂the␈α⊃text␈α⊂to␈α⊃designate␈α⊂pattern
␈↓ α←␈↓matches.␈α≡In␈α≡the␈α≡current␈α∨context␈α≡the␈α≡pattern␈α≡matches␈α∨will␈α≡involve
␈↓ α←␈↓S-expressions;␈α∞they␈α∞can␈α∞match␈α∂any␈α∞well-formed␈α∞S-expression.␈α∞ For␈α∂a␈α∞further
␈↓ α←␈↓example,␈α⊂let␈α⊂␈↓α(A . (B . C))␈↓␈α⊂be␈α⊃␈↓α(␈↓λα␈↓α . ␈↓λβ␈↓α)␈↓␈α⊂then␈α⊂␈↓λα␈↓␈α⊂is␈α⊃␈↓αA␈↓␈α⊂and␈α⊂␈↓λβ␈↓␈α⊂is␈α⊃␈↓α(B . C)␈↓.␈α⊂ These
␈↓ α←␈↓variables are called ␈↓↓match-variables␈↓ or ␈↓↓meta-variables␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'Finally here's a BNF description of the full set of S-expressions.
␈↓"∀␈↓ α←␈↓␈↓ ∧L<sexpr> :: = <atom> | ␈↓α(␈↓<sexpr> . <sexpr>␈↓α) 
␈↓"∀␈↓ α←␈↓␈↓ β'Notice␈α∞that␈α∂if␈α∞we␈α∂allow␈α∞real␈α∞numbers␈α∂as␈α∞atoms␈α∂then␈α∞some␈α∂care␈α∞would
␈↓ α←␈↓need␈αto␈αbe␈αexercised␈αwhen␈αwriting␈αS-expressions.␈αFor␈αexample,␈αshould␈α␈↓α(3.1.2)␈↓
␈↓ α←␈↓be␈αinterpreted␈αas␈αthe␈αdotted␈αpair␈α␈↓α(3␈α.␈α1.2)␈↓,␈αas␈αthe␈αdotted␈αpair␈α␈↓α(3.1 . 2)␈↓,␈αor␈αis␈αit
␈↓ α←␈↓just␈α∂an␈α∂ill-formed␈α∂expression?␈α∂ Interpretation␈α∂of␈α∂such␈α∂ambiguous␈α∞constructs
␈↓ α←␈↓will depend on the implementation; such details are discussed later.











␈↓"β␈↓ α←␈↓________________
␈↓"β␈↓ α←␈↓␈↓ β'␈↓π 3␈↓We will not give the termination clause, but it is assumed to hold.
␈↓ α←␈↓␈↓␈↓ 	KINDEX     3␈↓









␈↓ α←␈↓␈↓	Index␈↓












␈↓ α←␈↓dotted-pairs   2
␈↓ α←␈↓literal atoms   1
␈↓ α←␈↓match-variable   2
␈↓ α←␈↓meta-variables   2
␈↓ α←␈↓S-expressions   1
␈↓ α←␈↓S-exprs   1
␈↓ α←␈↓Symbolic expressions   1